資料結構 - 我好想懂阿！30 天系列 (23) - OBST (2)

14th鐵人賽

PogLotti

2022-10-07 15:40:49

4473 瀏覽

分享至

前言

前一篇文章有先提到我們要使用 Dynamic Programming 來找出 OBST，這章節就要告訴大家怎麼來找啦，但在進入怎麼找之前，我們先來了解一些符號，確保我們有共通的語言來看！

你必須要知道的符號

$a_{i+1}......a_{j}$ ：為內部節點
$p_{i+1}......p_{j}$ ：為內部節點加權值
$q_{i},q_{i+1}......q_{j}$ ：外部節點的加權值，這邊要注意，因為外部節點會比內部節點多一顆，所以權值也會多一個
$T_{i,j}=a_{i+1}......a_{j}$ 所構成的OBST，要注意是由 $a_{i+1}$ node 開始喔
$c_{i,j}=t_{i,j}$ 的 Cost
$w_{i,j}=t_{i,j}$ 的加權值總合
$r_{i,j}=t_{i,j}$ 的root

如何推導 Solution 公式

我們先想想，想要找出總搜尋成本最小的BST，就是要找出由 $a_{i+1}......a_{j}$ 組成的BST中最小的Cost
那要怎麼作，我們先來求 Cost，先令 $a_k$ 為此樹的 Root
則左子樹： $a_{i+1}...a_{k-1}=t_{i,k-1}$
右子樹： $a_{k+1}...a_{j}=t_{k,j}$
左子樹的 cost：若只單看左子樹，那成本就是 $c_{i,k-1}$ ，然而，實際狀況是多了一個 Root，因此每個節點 level 都會多 1，所以要加上該子樹所有點的權重，才會等於實際左子樹的 cost，也就是 $cost=c_{i,k-1}+w_{i,k-1}$
右子樹的 cost：若只單看右子樹，那成本就是 $c_{k,j}$ ，然而，實際狀況是多了一個 Root，因此每個節點 level 都會多 1，所以要加上該子樹所有點的權重，才會等於實際右子樹的 cost，也就是 $c_{k,j}+w_{k,j}$
因此整顆樹的Cost可以看成，左子樹 cost、右子樹 cost、root cost 加起來的結果
$c_{i,j}=1*p_{k}+c_{i,k-1}+c_{k,j}+w_{i,k-1}+w_{k,j}$
我們可以化簡一下，把式子簡化成 $c_{i,j}=w_{i,j}+c_{i,k-1}+c_{k,j}$ ，就是我們的cost Solution
接下來，我們只要精心挑選一個合適的 root k 就可以讓搜尋總成本降到最低囉
我們可以把式子看成這樣 $c_{i,j}=w_{i,j}+min\{c_{i,k-1}+c_{k,j}\}$